À cause de son manque d'enthousiasme à travailler autant dans les matières classiques que dans les matières scientifiques, Turing échoue plusieurs fois à ses examens. Il n'est admis qu'au King's College de l'université de Cambridge, alors qu'il avait demandé Trinity College en premier choix. Il étudie de 1931 à 1934 sous la direction de Godfrey Harold Hardy, mathématicien alors titulaire de la chaire sadleirienne puis responsable du centre de recherches et d'études en mathématiques. Il suit également les cours d'Arthur Eddington et, la dernière année, de Max Newman qui l'initie à la logique mathématique. En 1935, Turing est élu fellow du King's College, l'équivalent d'une bourse de thèse, grâce à sa démonstration du théorème central limite. En 1928, l'Allemand David Hilbert énonce le problème de la décision — connu sous le nom allemand d'« Entscheidungsproblem ») —. Pour cela il se place dans les théories axiomatiqueset demande s'il est possible de trouver une méthode « effectivement calculable » pour décider si une proposition est démontrable. Pour résoudre ce problème, il faut caractériser ce qu'est un procédé effectivement calculable. C'est ce que fait Turing dans son remarquable article de 1936, « On Computable Numbers, with an Application to the Entscheidungsproblem », en imaginant, non une machine matérielle, mais un « être calculant », qui peut être indifféremment un appareil logique très simple ou un humain bien discipliné appliquant des règles — comme le faisaient les employés des bureaux de calcul ou les artilleurs à l'époque. Dans le cours de son raisonnement, il démontre que le problème de l'arrêt d’une machine de Turing ne peut être résolu par algorithme : il n’est pas possible de décider avec un algorithme (c’est-à-dire avec une machine de Turing) si une machine de Turing donnée s’arrêtera. Bien que sa preuve ait été publiée après celle d'Alonzo Church, le travail de Turing est plus accessible et intuitif. Il est aussi complètement nouveau dans sa présentation du concept de « machine universelle » (de Turing), avec l'idée qu'une telle machine puisse accomplir les tâches de n'importe quelle autre machine. L'article présente également la notion de nombre réel calculable. Il déduit de l'indécidabilité du problème de l'arrêt que l'on peut définir des nombres réels qui ne sont pas calculables. Il introduit les concepts de programme et de programmation. Turing passe la plus grande partie de 1937 et de 1938 à travailler sur divers sujets à l'université de Princeton, sous la direction du logicien Alonzo Church qui a déjà encadré le travail de Stephen Kleene sur la récursivité. Il obtient en mai 1938 son Ph.D. de l'université de Princeton ; son manuscrit présente la notion d'hypercalcul, où les machines de Turing sont complétées par ce qu'il appelle des oracles, autorisant ainsi l'étude de problèmes qui ne peuvent pas être résolus de manière algorithmique. L'appellation de « machine de Turing » vient de Church, son directeur de thèse, qui l'emploie pour la première fois dans un compte-rendu du travail de son élève dans le Journal of Symbolic Logic. Turing obtient des résultats importants sur le lambda-calcul, notamment en montrant son équivalence avec son propre modèle de calculabilité, en inventant le combinateur de point-fixe qui porte son nom et en proposant la première démonstration de la normalisation du lambda calcul typé. De retour à Cambridge en 1939, il assiste à des cours publics de Ludwig Wittgenstein sur les fondements des mathématiques. Tous deux discutent avec véhémence et constatent leur désaccord, Turing défendant le formalisme alors que Wittgenstein pense que les mathématiques sont surestimées et qu'elles ne permettent pas de découvrir une quelconque vérité absolue.